package wh.链表的中间节点;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/12/29 11:13
 * @description:返回链表的中间节点，如果有两个，返回后面这个
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        ListNode listNode = middleNode(head);
        System.out.println(listNode.next.val);
    }


    public static ListNode middleNode(ListNode head){
        ListNode p = head;
        int nodeNum = 0;
        int midNum = 0;
        while (p != null){
            nodeNum++;
            p = p.next;
        }
        System.out.println("该链表的长度为" + nodeNum);
        midNum = (nodeNum / 2) +1;
        int start = 1;
        ListNode q = head;
        while (start != midNum){
            q = q.next;
            start++;
        }
        return q;
    }

    //加上数组
    public static ListNode middleNode2(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }

    //快慢指针 slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间 妙！！
    public static ListNode middleNode3(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


}
